pub struct ShuDu {
    context: Vec<Vec<u8>>,
    //数独表格 按行列
    empty_count: usize,
    //空白个数
    col_step: usize,
    //列步长 9*9 是 3
    row_step: usize,
    //行步长 9*9 是 3
    row_num: usize,
    //行数
    col_num: usize, //列数
}

impl ShuDu {
    pub fn new9() -> ShuDu {
        let mut context = Vec::new();

        //传说中的最难数独
        let l1 = vec![4, 0, 7, 0, 0, 0, 0, 0, 8];
        let l2 = vec![0, 9, 0, 0, 5, 0, 0, 7, 4];
        let l3 = vec![0, 5, 0, 0, 0, 0, 6, 0, 2];
        let l4 = vec![0, 0, 0, 0, 7, 0, 0, 0, 6];
        let l5 = vec![0, 0, 0, 1, 0, 0, 9, 0, 0];
        let l6 = vec![0, 0, 0, 2, 6, 0, 5, 4, 7];
        let l7 = vec![2, 1, 0, 9, 0, 0, 0, 0, 0];
        let l8 = vec![0, 7, 0, 0, 0, 0, 0, 6, 0];
        let l9 = vec![6, 0, 0, 7, 0, 0, 0, 8, 9];
        context.push(l1);
        context.push(l2);
        context.push(l3);
        context.push(l4);
        context.push(l5);
        context.push(l6);
        context.push(l7);
        context.push(l8);
        context.push(l9);
        let mut empty_count = 0usize;
        for line in &context {
            for item in line {
                if 0 == *item {
                    empty_count += 1;
                }
            }
        }
        ShuDu {
            context: context,
            empty_count: empty_count,
            col_step: 3,
            row_step: 3,
            row_num: 9,
            col_num: 9,
        }
    }
    //设置指定位置location(row,col)的值
    pub fn set_location_value(&mut self, location: (usize, usize), value: u8) {
        self.context[location.0][location.1] = value;
        self.empty_count -= 1;
    }
    //重设指定位置location(row,col)的值
    pub fn reset_location_value(&mut self, location: (usize, usize)) {
        self.context[location.0][location.1] = 0u8;
        self.empty_count += 1;
    }
    //获得某个位置location(row,col)可能的值
    fn get_condianates(&self, location: (usize, usize)) -> Vec<u8> {
        let mut _count = 0;
        // bool 数组，元素为 false 表示当前索引值不冲突，可以作为候选值
        let mut flag = Vec::<bool>::new();
        for _i in 0..self.col_step * self.row_step {
            flag.push(false);
        }

        //排除行冲突的值
        for row in 0..self.row_num {
            let value = self.context[row][location.1];
            //print!("{:?} ",value);
            if 0 != value && location.0 != row {
                // print!("{:?} ",value);
                _count += 1;
                flag[(value - 1) as usize] = true;
            }
        }
        //println!("");
        //排除列冲突的值
        for col in 0..self.col_num {
            let value = self.context[location.0][col];
            //print!("{:?} ",value);
            if 0 != value && location.1 != col {
                //print!("{:?} ",value);
                flag[(value - 1) as usize] = true;
            }
        }
        //println!("");
        //排除周围冲突的值
        let row_start: usize = {
            (location.0 / self.row_step) * self.row_step
        };
        let row_end = row_start + self.row_step;

        let col_start: usize = {
            (location.1 / self.col_step) * self.col_step
        };
        let col_end = col_start + self.col_step;
        //print!("row_start:{:?},row_end:{:?},col_start:{:?},col_end:{:?} ",row_start,row_end,col_start,col_end);
        for row in row_start..row_end {
            // println!("");
            for col in col_start..col_end {
                let value = self.context[row][col];
                //print!("{:?} ",value);
                if 0 != value && location != (row, col) {
                    _count += 1;
                    flag[(value - 1) as usize] = true;
                }
            }
        }
        //索引转为数字
        let mut candiantes = Vec::<u8>::new();
        let mut cand = 1u8;
        for v in flag {
            if !v {
                candiantes.push(cand);
            }
            cand += 1;
        }
        candiantes
    }

    //获得候选值最少的位置
    pub fn get_best_location(&mut self) -> (usize, usize) {
//        let row = 0usize;
//        let col = 0usize;
        let mut cand_count = self.col_step * self.row_step;
        let mut best_cand_location = (0usize, 0usize);
        for row in 0..self.row_num {
            for col in 0..self.col_num {
                if 0 == self.context[row][col] {
                    let candinates = self.get_condianates((row, col));
                    //println!("{:?},{:?}",(row,col),candinates);
                    if cand_count > candinates.len() {
                        cand_count = candinates.len();
                        best_cand_location = (row, col);
                    }
                    if 1 == cand_count {
                        return best_cand_location;
                    }
                }
            }
        }
        return best_cand_location;
    }

    //是否解决了
    pub fn is_solved(&self) -> bool {
        return 0 == self.empty_count;
    }
}

//回溯，深度优先遍历
pub fn back_trace(sudoku: &mut ShuDu) {
    if sudoku.is_solved() {
        for line in &sudoku.context {
            for item in line {
                print!("{:?} | ", item);
                if Some(item) == line.last() {
                    println!("\n-----------------------------------");
                }
            }
        }
        return;
    } else {
        //获得候选 最少的位置进行填写
        let best_location = sudoku.get_best_location();
        let candinates = sudoku.get_condianates(best_location);
        for value in candinates {
            sudoku.set_location_value(best_location, value);
            back_trace(sudoku);
            sudoku.reset_location_value(best_location);
        }
    }
}

pub fn shu_du_test() {
    let mut shu_du = ShuDu::new9();
    back_trace(&mut shu_du);
}